knapsack problem

American  

noun

Mathematics.

1. the problem of determining which numbers from a given collection of numbers have been added together to yield a specific sum: used in cryptography to encipher (and sometimes decipher) messages.

---

Etymology

Origin of knapsack problem

So called because the problem is similar to determining what packages are in a closed knapsack when the weights of the individual packages and the filled knapsack are known

Example Sentences

If you come up with a fast way to do the knapsack problem, you could directly apply that algorithm to the Traveling Salesman problem and vice versa.

From Slate • Feb. 9, 2016